package com.jjlin.chapter_3;

import java.util.*;
public class CD182{
    public static int mod = (int)1e9 + 7;
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    public static List<Node> generateTrees(int n){
        if(n < 2){
            List<Node> res = new ArrayList<>();
            if(n < 1)
                res.add(null);
            else
                res.add(new Node(1));
            return res;
        }
        return generate(1, n);
    }

    //生成CD181的所有不同二叉树的集合(集合中包含的是二叉树head节点)
    //这种写法只是为了扩展作用，在实际测试中由于时间复杂度多大，无法通过，通过的代码参见讨论区
    public static List<Node> generate(int start, int end){
        List<Node> res = new ArrayList<Node>();
        if(start > end)
            res.add(null);
        Node head = null;
        for(int i = start; i <= end; i++){
            head = new Node(i);//以i为根节点的二叉树
            List<Node> lsub = generate(start, i - 1);//左子树集合
            List<Node> rsub = generate(i + 1, end);//右子树集合
            for(Node l : lsub){
                for(Node r : rsub){
                    head.left = l;
                    head.right = r;
                    res.add(cloneTree(head));
                }
            }
        }
        return res;
    }

    //克隆一颗二叉树
    public static Node cloneTree(Node node){
        if(node == null)
            return node;
        Node cloneNode = new Node(node.val);
        cloneNode.left = cloneTree(node.left);
        cloneNode.right = cloneTree(node.right);
        return cloneNode;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Node> res = generateTrees(n);
        System.out.println(res.size() % mod);
    }
}
